home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / awe2-0_1.lha / awe2-0.1 / Src / RCS / SharedMalloc-real.cc,v < prev    next >
Text File  |  1989-05-16  |  12KB  |  514 lines
  1. head     3.2;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    grunwald:3.2; strict;
  6. comment  @@;
  7.  
  8.  
  9. 3.2
  10. date     89.02.20.15.37.16;  author grunwald;  state Exp;
  11. branches ;
  12. next     3.1;
  13.  
  14. 3.1
  15. date     88.12.20.13.49.11;  author grunwald;  state Exp;
  16. branches ;
  17. next     1.2;
  18.  
  19. 1.2
  20. date     88.10.30.13.04.33;  author grunwald;  state Exp;
  21. branches ;
  22. next     1.1;
  23.  
  24. 1.1
  25. date     88.09.28.22.13.33;  author grunwald;  state Exp;
  26. branches ;
  27. next     ;
  28.  
  29.  
  30. desc
  31. @@
  32.  
  33.  
  34. 3.2
  35. log
  36. @Start using Gnu library heaps for schedulers
  37. @
  38. text
  39. @// This may look like C code, but it is really -*- C++ -*-
  40. // 
  41. // Copyright (C) 1988 University of Illinois, Urbana, Illinois
  42. //
  43. // written by Dirk Grunwald (grunwald@@cs.uiuc.edu)
  44. //
  45. //
  46. // Allocator.c: based loosely on...
  47. //
  48. // malloc.c (Caltech) 2/21/82
  49. // Chris Kingsley, kingsley@@cit-20.
  50. //
  51. //    $Header: /mntm/4/reed/grunwald/Awe2/Src/RCS/SharedMalloc-real.cc,v 3.1 88/12/20 13:49:11 grunwald Exp $
  52. //
  53. // This is a very fast storage allocator.  It allocates blocks of a small 
  54. // number of different sizes, and keeps free lists of each size. In this 
  55. // implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  56. // 
  57.  
  58. #define NDEBUG
  59.  
  60. #include "Debug.h"
  61. #include "assert.h"
  62. #include "CpuMultiplexor.h"
  63. #include <stdio.h>
  64. #include <stream.h>
  65.  
  66. PRAGMA_LINKAGE_C
  67.  
  68. extern char *sbrk(int);
  69. extern void exit(int x = 0);
  70. char *malloc( unsigned );
  71. void free(char *);
  72.  
  73. PRAGMA_LINKAGE
  74.  
  75. const int NOTREACHED = 0;
  76.  
  77. extern int CpuMuxDebugFlag;
  78.  
  79. //
  80. //    calloc and cfree are defined in terms of malloc.
  81. //    alloca allocates space from the current stack.
  82. //
  83.  
  84. #include "assert.h"
  85. #include "SpinLock.h"
  86.  
  87. //
  88. // Allocator.h: based loosely on...
  89. //
  90. // malloc.c (Caltech) 2/21/82
  91. // Chris Kingsley, kingsley@@cit-20.
  92. //
  93. //    $Header: /mntm/4/reed/grunwald/Awe2/Src/RCS/SharedMalloc-real.cc,v 3.1 88/12/20 13:49:11 grunwald Exp $
  94. //
  95. // 
  96.  
  97. //
  98. // Below is a allocator sbuclass based loosely on..
  99. //
  100. // malloc.c (Caltech) 2/21/82
  101. // Chris Kingsley, kingsley@@cit-20.
  102. //
  103. // This is a very fast storage allocator.  It allocates blocks of a small 
  104. // number of different sizes, and keeps free lists of each size. In this 
  105. // implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  106. // 
  107.  
  108. //
  109. // The overhead on a block is at least 4 bytes.  When free, this space
  110. // contains a pointer to the next free block, and the bottom two bits must
  111. // be zero.  When in use, the first byte is set to MAGIC, and the second
  112. // byte is the size index.  The remaining bytes are for alignment.
  113. // If range checking is enabled and the size of the block fits
  114. // in two bytes, then the top two bytes hold the size of the requested block
  115. // plus the range checking words, and the header word MINUS ONE.
  116. // 
  117. union    overhead {
  118.     union    overhead * ov_next;    // when free
  119.     struct {
  120.     unsigned char    ovu_magic;    // magic number
  121.     unsigned char    ovu_index;    // bucket #
  122.     unsigned short    ovu_size;    // actual block size
  123.     unsigned int    ovu_rmagic;    // range magic number
  124.     } ovu;
  125. };
  126.  
  127. #define    ov_magic    ovu.ovu_magic
  128. #define    ov_index    ovu.ovu_index
  129. #define    ov_size        ovu.ovu_size
  130. #define    ov_rmagic    ovu.ovu_rmagic
  131.  
  132. #define    MAGIC        0xff        /* magic # on accounting info */
  133. #define RMAGIC        0x55555555    /* magic # on range info */
  134. #define    RSLOP        sizeof( unsigned int )
  135.  
  136. //
  137. // nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  138. // smallest allocatable block is 8 bytes.  The overhead information
  139. // precedes the data area returned to the user.
  140. // 
  141.  
  142. int const NumberOfBuckets = 30;
  143.  
  144. class BucketAllocator {
  145. protected:
  146.     union overhead * nextf[ NumberOfBuckets ];
  147.     SpinLock bucketLock[ NumberOfBuckets ];
  148.     
  149.     SpinLock topLock;
  150.     char * top;
  151.  
  152.     char sbrkDisabled;
  153.     char initialized;
  154.     
  155.     int morecore( int bucket );
  156.  
  157.     void initialize();
  158. public:
  159.     BucketAllocator();
  160.     ~BucketAllocator();
  161.     void * allocate( unsigned nbytes );
  162.     void free( void * cp );
  163.     void disableFurtherBreaks();
  164. };
  165.  
  166. BucketAllocator HardwareMemoryAllocator;
  167.  
  168. PRAGMA_LINKAGE_C
  169.  
  170. char *malloc( unsigned size)
  171. {
  172.     return( ( char * )HardwareMemoryAllocator.allocate( size ) );
  173. }
  174.  
  175. void free(char * ptr)
  176. {
  177.     HardwareMemoryAllocator.free( (void *) ptr );
  178. }
  179.  
  180. PRAGMA_LINKAGE
  181.     
  182. BucketAllocator::BucketAllocator()
  183. {
  184.     initialize();
  185. }
  186.  
  187. void
  188. BucketAllocator::disableFurtherBreaks()
  189. {
  190.     sbrkDisabled = 1;
  191. }
  192.  
  193. void disableFurtherBreaks()
  194. {
  195.     HardwareMemoryAllocator.disableFurtherBreaks();
  196. }
  197.  
  198. void
  199. BucketAllocator::initialize()
  200. {
  201.     if (initialized) return;
  202.     //
  203.     // First allocate the state information for the object from the
  204.     // sourceMemoryObjectCache.
  205.     // 
  206.  
  207.     for( int i = 0; i < NumberOfBuckets; i++ ) {
  208.     nextf[ i ] = 0;
  209.     }
  210.     
  211.     extern int end;
  212.     top = (char *) &end;
  213.     sbrkDisabled = 0;
  214.     initialized = 1;
  215. }
  216.  
  217. //
  218. //    Deleteing the allocator doesn't free up your memory, it just
  219. //    makes us forget about it. However, this is only done when
  220. //    you call exit, so who cares.
  221. //
  222. BucketAllocator::~BucketAllocator()
  223. {
  224. }
  225.  
  226. void *
  227. BucketAllocator::allocate( unsigned nbytes )
  228. {
  229.     if (!initialized) {
  230.     initialize();
  231.     }
  232.  
  233.     union overhead * p;
  234.     int bucket = 0;
  235.     unsigned shiftr;
  236.  
  237. #ifndef NDEBUG    
  238.     if (CpuMuxDebugFlag) {
  239.     cerr << "BucketAllocator::allocate( " << nbytes;
  240.     cerr << " ) for top = " << hex(long(top)) << "\n";
  241.     }
  242. #endif
  243.     //
  244.     // Convert amount of memory requested into
  245.     // closest block size stored in hash buckets
  246.     // which satisfies request.  Account for
  247.     // space used per block for accounting.
  248.     // 
  249.     nbytes += sizeof( union overhead ) + RSLOP;
  250.     nbytes = ( nbytes + 3 ) &~ 3; 
  251.     shiftr = ( nbytes - 1 ) >> 2;
  252.     // apart from this loop, this is O(1) */
  253.      while( shiftr >>= 1 )
  254.      bucket++;
  255.     
  256.     Debug( "BucketAllocator::allocate: nbytes=%x, shiftr=%x, bucket=%x\n",
  257.       nbytes, shiftr, bucket );
  258.     assert( bucket < NumberOfBuckets );
  259.     
  260.     //
  261.     // If nothing in hash bucket right now, request more memory from
  262.     // the system.
  263.     // This is probably pathalogical (?) and can lead to one processor
  264.     // always allocation memory for everybody else, but hopefully the
  265.     // locks will make it somewhat fairer.
  266.     // 
  267.     Debug( "BucketAllocator::allocate: waiting on bucket %d lock\n",
  268.       bucket );
  269.     bucketLock[bucket].reserve();
  270.     while( nextf[ bucket ] == 0 ) {
  271.     Debug( "BucketAllocator::allocate: filling bucket %d\n",
  272.           bucket );
  273.     bucketLock[bucket].release();
  274.     if( ! morecore( bucket ) )
  275.         break;
  276.     bucketLock[bucket].reserve();
  277.     }
  278.     Debug( "BucketAllocator::allocate: nextf[bucket] = %x\n",
  279.       nextf[bucket] );
  280.     if( nextf[bucket] == 0 ) {
  281.     fprintf(stderr, "BucketAllocator::allocate REALLY out of memory\n" );
  282.     bucketLock[bucket].release();
  283.     return( 0 );
  284.     }
  285.     
  286.     //
  287.     // Grab the next entry in the bucket.
  288.     // 
  289.     p = nextf[ bucket ];
  290.     Debug( "BucketAllocator::allocate: p = %x\n", p );
  291.     
  292.     //
  293.     // remove from linked list
  294.     // 
  295.     nextf[ bucket ] = nextf[ bucket ]->ov_next;
  296.     bucketLock[bucket].release();
  297.     
  298.     p->ov_magic = MAGIC;
  299.     p->ov_index= bucket;
  300.     
  301.     //
  302.     // Record allocated size of block and
  303.     // bound space with magic numbers.
  304.     // 
  305.     if( nbytes <= 0x10000 )
  306.     p->ov_size = nbytes - 1;
  307.     p->ov_rmagic = RMAGIC;
  308.     *((unsigned int *) ((char *) p + nbytes - RSLOP)) = RMAGIC;
  309.     
  310.     Debug( "BucketAllocator::allocate: returning %A\n", (char *) (p + 1) );
  311.     return( (char *) (p + 1) );
  312. }
  313.  
  314. //
  315. // Get more memory into a bucket. Also prefetch the memory.
  316. // 
  317. int
  318. BucketAllocator::morecore( int bucket )
  319. {
  320.     union overhead * op;
  321.     int rnu;       // 2^rnu bytes will be requested
  322.     int nblks;     // become nblks blocks of the desired size
  323.     int siz;
  324.     
  325.     Debug( "BucketAllocator::morecore( bucket:%d )\n", bucket );
  326.     
  327.     //
  328.     // take PAGESIZE (4k) unless the block is bigger than that
  329.     //
  330.     
  331.     rnu = ( bucket <= 9 ) ? 12 : bucket + 3;
  332.     nblks = 1 << ( rnu - ( bucket + 3 ) );  // how many blocks to get
  333.     if( rnu < bucket )
  334.     rnu = bucket;
  335.     
  336.     Debug( "BucketAllocator::morecore(): getting %d bytes\n", 1 << rnu );
  337.     
  338.     //
  339.     // See if there is room left in the cached space for the request.
  340.     // 
  341.     topLock.reserve();
  342.     int nbytes = 1 << rnu;
  343.     
  344.     char *highest = sbrk(0);
  345.     
  346.     if ( ( top + nbytes ) > highest ) {
  347.     if ( sbrkDisabled ) {
  348.  
  349.         cerr << "BucketAllocator::morecore: out of memory\n";
  350.         cerr << "top     = " << hex(long(top)) << "\n";
  351.         cerr << "highest = " << hex(long(highest)) << "\n";
  352.         cerr << "sbrk(0) = " << hex(long(sbrk(0))) << "\n";
  353.  
  354.         topLock.release();
  355.  
  356.         return( 0 );
  357.     }
  358.     else {
  359.         //
  360.         //    Get more space & reduce the number of system calls.
  361.         //
  362.         highest = sbrk(nbytes * 2);
  363.     }
  364.     }
  365.     
  366.     op = (union overhead *) top;
  367.     top += nbytes;
  368.     topLock.release();
  369.     //
  370.     // Round up to minimum allocation size boundary
  371.     // and deduct from block count to reflect.
  372.     // 
  373.     if( (int) op & 7 ) {
  374.     op = (union overhead *) (((int)op + 8) &~ 7);
  375.     nblks--;
  376.     }
  377.     Debug( "BucketAllocator::morecore(): adjusted op = %x\n", op );
  378.     
  379.     //
  380.     // Add new memory allocated to that on
  381.     // free list for this hash bucket.
  382.     // 
  383.     siz = 1 << ( bucket + 3 );
  384.     
  385.     union overhead * block = op;
  386.     
  387.     Debug( "BucketAllocator::morecore(): nblks = %d  size = %d\n",
  388.       nblks, siz );
  389.     while( --nblks > 0 ) {
  390.     block->ov_next = (union overhead *) ( (char *) block + siz );
  391.     block = (union overhead *) ( (char *) block + siz );
  392.     }
  393.     Debug( "BucketAllocator::morecore(): adding new memory to bucket %d\n",
  394.       bucket );
  395.     
  396.     bucketLock[bucket].reserve();
  397.     
  398.     block->ov_next = nextf[ bucket ];    // terminate the list with
  399.     // anything that was already 
  400.     // there..
  401.     nextf[ bucket ] = op;
  402.     
  403.     bucketLock[bucket].release();
  404.     return( 1 );
  405. }
  406.  
  407. //
  408. // Return memory to the free pool.
  409. // Currently this does not return the physical pages associated with the
  410. // memory, but it should.
  411. // 
  412. void
  413. BucketAllocator::free( void * cp )
  414. {   
  415.     int bucket;
  416.     union overhead *op;
  417.     
  418.     Debug( "BucketAllocator::free( %x )\n", cp );
  419.     if( cp == 0 )
  420.     return;
  421.     op = (union overhead *) ( (char *) cp - sizeof( union overhead ) );
  422.  
  423.     assert( op->ov_magic == MAGIC );    // make sure it was in use
  424.     assert( op->ov_rmagic == RMAGIC );
  425.  
  426.     if( op->ov_index <= 13 )
  427.     assert( *(unsigned int *)((char *)op + op->ov_size + 1 - RSLOP) == RMAGIC );
  428.  
  429.     assert( op->ov_index < NumberOfBuckets );
  430.     bucket = op->ov_index;
  431.     bucketLock[bucket].reserve();
  432.     op->ov_next = nextf[ bucket ];
  433.     nextf[ bucket ] = op;
  434.     bucketLock[bucket].release();
  435. }
  436. @
  437.  
  438.  
  439. 3.1
  440. log
  441. @Steay version
  442. @
  443. text
  444. @d13 1
  445. a13 1
  446. //    $Header: /import/max/reed/grunwald/Awe2/Src/RCS/SharedMalloc-real.cc,v 1.2 88/10/30 13:04:33 grunwald Exp Locker: grunwald $
  447. d55 1
  448. a55 1
  449. //    $Header: /import/max/reed/grunwald/Awe2/Src/RCS/SharedMalloc-real.cc,v 1.2 88/10/30 13:04:33 grunwald Exp Locker: grunwald $
  450. @
  451.  
  452.  
  453. 1.2
  454. log
  455. @*** empty log message ***
  456. @
  457. text
  458. @d13 1
  459. a13 1
  460. //    $Header: SharedMalloc-real.cc,v 1.1 88/09/28 22:13:33 grunwald Exp $
  461. d28 2
  462. d32 2
  463. d35 2
  464. a40 2
  465. char *malloc( unsigned );
  466. void free(char *);
  467. d55 1
  468. a55 1
  469. //    $Header: SharedMalloc-real.cc,v 1.1 88/09/28 22:13:33 grunwald Exp $
  470. d130 2
  471. d136 1
  472. d141 2
  473. @
  474.  
  475.  
  476. 1.1
  477. log
  478. @Initial revision
  479. @
  480. text
  481. @d1 3
  482. d5 3
  483. d13 1
  484. a13 1
  485. //    $Header: SharedMalloc.cc,v 1.2 88/09/21 20:51:39 grunwald Exp $
  486. d20 2
  487. d24 1
  488. a24 1
  489. #include "HardwareCpu.h"
  490. d28 1
  491. a28 1
  492. extern char *sbrk(unsigned);
  493. d33 1
  494. a33 1
  495. extern int HardwareDebugFlag;
  496. d43 1
  497. a43 1
  498. #include "HardSpinLock.h"
  499. d51 1
  500. a51 1
  501. //    $Header: SharedMalloc.h,v 1.1 88/09/18 16:42:15 grunwald Exp $
  502. d105 1
  503. a105 1
  504.     HardSpinLock bucketLock[ NumberOfBuckets ];
  505. d107 1
  506. a107 1
  507.     HardSpinLock topLock;
  508. d189 3
  509. a191 2
  510.     
  511.     if (HardwareDebugFlag) {
  512. d195 1
  513. @
  514.